Embodiments of the invention are in the field of digital data communications, and is more specifically directed to Low-Density Parity-Check (LDPC) codes and a scalable decoder architecture.
A problem common to digital data communication technology is the likelihood of data corruption. Data is usually corrupted by noise occurring in the communication channel. The noise interferes with the signal carrying the data over the channel, causing errors in the data bits, or symbols. As is fundamental in the art, the signal-to-noise ratio for a communications channel is a degree of goodness of the communications carried out over that channel, as it conveys the relative strength of the signal that carries the data (as attenuated over distance and time), to the noise present on that channel. These factors relate directly to the likelihood that a data bit or symbol received over the channel will be in error relative to the data bit or symbol as transmitted. This likelihood is reflected by the error probability for the communications over the channel, commonly expressed as the Bit Error Rate (BER) ratio of errored bits to total bits transmitted. In short, the likelihood of error in data communications must be considered in developing a communications technology. Techniques for detecting and correcting errors in the communicated data must be incorporated for the communications technology to be useful.
Various techniques for detecting and correcting errors in the bits have been developed. At least some error detection and correction techniques are implemented through redundant coding of the bits. For example, parity bits may be inserted into the transmitted data stream sent over the communication channel. These parity bits do not add any additional information, but can be cross-referenced to detect and correct errors in the values of other bits. Of course, these parity bits are also prone to errors. As another example, a code may repeat the transmission; for instance, the payload is sent three times. The receiver deduces the payload by using a decoder to determine which bit in each position was received two or more times. The drawback of such a decoder is that if a bit is received erroneously two or more times, the decoder will select the erroneous bit as correct. There is tradeoff between decoder architecture complexity and bit error rate. A desire for a lower bit error rate typically results in higher complexity decoder architecture than would be the case if a higher bit error rate was permitted. An architecture, system, or method that results in a less complex decoder while maintaining a low the bit error rate is desirable.
Error detection and correction techniques are typically implemented through the use of redundant coding of the data. In general, redundant coding inserts data bits into the transmitted data stream that do not add any additional information, but that indicate whether an error is present in the received data stream. More complex codes provide the ability to deduce the true transmitted data from a received data stream, despite the presence of errors.
Many types of redundant codes that provide error correction have been developed. One type of code simply repeats the transmission, for example repeating the payload twice, so that the receiver deduces the transmitted data by applying a decoder that determines the majority vote of the three transmissions for each bit. Of course, this simple redundant approach does not necessarily correct every error, but greatly reduces the payload data rate. In this example, a predictable likelihood remains that two of three bits are in error, resulting in an erroneous majority vote despite the useful data rate having been reduced to one-third. More efficient approaches, such as Hamming codes, have been developed toward the goal of reducing the error rate while maximizing the data rate.
Another class of known redundant codes is the Low Density Parity Check code. Low-Density Parity-Check (LDPC) codes are linear block codes with sparse parity check matrices. Their asymptotic performance can be as close to one tenth dB away from the Shannon limit. Another advantage of LDPC codes is that the decoding algorithm is inherently parallel and so a wide variety of hardware implementations can be derived that exploit this feature. Because of their extraordinary performance, LDPC codes have been adopted in many recent communication standards such as DVB-S2, 10GBase-T, 802.16 and 802.11n, etc. LDPC codes are also serious candidates for many storage applications.
Existing LDPC decoders can only handle sub-matrix degree W=1 with reasonable complexity. If W is larger than 1, then the decoding complexity dramatically increases. Thus it limited many high performance LDPC codes from being implemented in real systems. A general decoder architecture that can handle LDPC codes with higher sub-matrix degree is still missing and needs to be developed for future applications on LDPC codes. There is a need for an algorithm and scalable decoder architecture to handle W>=1 case.